package leetcode.code1601;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution1 implements IDebug {

	int limit;
	int[][] requests;
	int len;
	int ans;

	public int maximumRequests(int n, int[][] requests) {
		this.len = requests.length;
		this.limit = (1 << len) - 1;
		this.requests = requests;
		this.ans = 0;
		int used = 0;
		for (int i = 0; i < len; i++) {
			int[] cur = requests[i];
			if (cur[0] == cur[1]) {
				this.ans += 1;
				used |= 1 << i;
			}
		}
		Integer[][][] dp = new Integer[n + 1][len + 1][1 << len];
		this.find(ans, 0, used, 0, 1, dp);
		return this.ans;
	}

	private void find(int ok, int index, int used, int start, int size, Integer[][][] dp) {
		if (index == len) {
			this.ans = Math.max(this.ans, ok);
			dp[ok][index][used] = this.ans;
			return;
		}
		if (dp[ok][index][used]!= null) {
			return;
		}
		if ((used & (1 << index)) != 0) {
			this.find(ok, index + 1, used, index + 1, 1, dp);
			return;
		}
		int[] cur = requests[index];
		used |= 1 << index;
		int useful = this.limit ^ used;
		if (cur[1] == requests[start][0]) {
			ok += size;
			while (useful > 0) {
				int tryUse = (int) (Math.log(useful & -useful) / Math.log(2));
				this.find(ok, tryUse, used, tryUse, 1, dp);
				useful -= 1 << tryUse;
			}
		} else {
			while (useful > 0) {
				int tryUse = (int) (Math.log(useful & -useful) / Math.log(2));
				int[] tryRequest = requests[tryUse];
				if (tryRequest[0] == cur[1]) {
					this.find(ok, tryUse, used, start, size + 1, dp);
				} else {
					this.find(ok, start + 1, used, start + 1, 1, dp);
				}
				useful -= 1 << tryUse;
			}
		}
		this.ans = Math.max(this.ans, ok);
		dp[ok][index][used] = this.ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(5, this.maximumRequests(5, HelpDebug.str2array1("[[3,4],[1,0],[0,1],[0,1],[1,2],[2,0]]")));
	}

	@Override
	public void debug2() {
		HelpDebug.compare(3, this.maximumRequests(3, HelpDebug.str2array1("[[0,0],[1,2],[2,1]]")));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
//		20
//		[[0,3],[0,0],[0,1],[1,2],[2,1],[3,4],[7,9],[15,14],[13,14],[16,11],[9,10],[9,11],[11,7]]
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug2();
		so.debug1();
		so.debug3();
		so.debug4();

	}

}
